#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <string>

#define IS_FULL(ptr) (!(ptr))

using namespace std;

typedef struct node *tree_ptr;		// node pointer
typedef struct node{
	tree_ptr llink;					// struct node has left-link part, right-link part, and key part
	tree_ptr rlink;
	int key;
	int bf;
};

int unbalanced = false;

typedef struct str *string_ptr;	// string pointer
typedef struct str {				// struct string has string name part and tree pointer part
	tree_ptr link;
} str;


// function declarations
tree_ptr insert_node(int X, tree_ptr T);
void left_rotation(tree_ptr T);
void right_rotation(tree_ptr T);

void	preorder(tree_ptr node),
	inorder(tree_ptr node),
	postorder(tree_ptr node);



bool flag_arrow; // flag for check print arrow or not

int main()
{

	int location;
	int key, cip;
	string str_input;
	char comma;
	tree_ptr root;
	char input[1024];

	printf("Type numbers to input : ");				// input numbers to input by string
	gets(input);
	root = NULL;
	location = 0;

	do{
		sscanf(&input[location], "%d", &key);		// put data one by one

		unbalanced = false;
		root = insert_node(key, root); // insert at BST

		for(cip = key ; cip!=0 ; cip = cip / 10){
			location++;									// find cipher
		}
		location++;
		sscanf(&input[location++], "%c", &comma);

	}while(input[location-1] != NULL);

	//printf("%s inserted!!\n\n", input);
	flag_arrow = false;
	printf("\nPreorder: ");
	preorder(root);
	flag_arrow = false;
	printf("\nInorder: ");
	inorder(root);
	flag_arrow = false;
	printf("\nPostorder: ");
	postorder(root);
	printf("\n");


	printf("Thank you for using this software!!\n");		// good bye
}
/*
tree_ptr insert_node(int X, tree_ptr T)  
{  
if( T == NULL )  
{  
// Create and return a one-node tree
T = (tree_ptr)malloc( sizeof( struct node ) );  
if( T == NULL )  
printf( "Out of space!!!" );				// memory is full
else 
{  
T->key = X;             
T->llink = T->rlink = NULL; 
}
}  
else {
if( X < T->key )  
T->llink = insert_node( X, T->llink );  
else {
if( X > T->key )  
T->rlink = insert_node( X, T->rlink );
}
// Else X is in the tree already; we'll do nothing 
}
return T;  // return tree_ptr T
}  */

tree_ptr insert_node(int X, tree_ptr T)  
{
	if(T == NULL){
		unbalanced = false;
		T = T = (tree_ptr)malloc( sizeof( struct node ) );
		if( T == NULL )  
			printf( "Out of space!!!" );				// memory is full
		else 
		{  
			T->key = X;             
			T->llink = T->rlink = NULL;
			T->bf = 0;
		}
	}
	else if(X < T->key){
		T->llink = insert_node(X, T->llink);
		if(unbalanced){
			switch(T->bf){
			case -1:
				T->bf = 0;
				unbalanced = false;
				break;
			case 0:
				T->bf = 1;
				break;
			case 1:
				left_rotation(T);
			}
		}
	}
	else if( X > T->key ){
		T->rlink = insert_node( X, T->rlink );
		if(unbalanced){
			switch(T->bf){
			case 1:
				T->bf = 0;
				unbalanced = false;
				break;
			case 0:
				T->bf = 1;
				break;
			case -1:
				right_rotation(T);
				break;
			}
		}
	}
	return T;
}

void left_rotation(tree_ptr T)
{
	tree_ptr grand_c, c;
	c = T->llink;

	if(c->bf == 1)
	{
		T->llink = c->rlink;
		c->rlink = T;
		T->bf = 0;
		T = c;
	}
	else
	{
		grand_c = c->rlink;
		c->rlink = grand_c->llink;
		grand_c->llink = c;
		T->llink = grand_c->rlink;
		grand_c->rlink = T;

		switch(grand_c->bf){
		case 1:
			T->bf = -1;
			c->bf = 0;
			break;
			
		case 0:
			T->bf = c->bf = 0;
			break;
		case -1:
			T->bf = 0;
			c->bf = 1;
		}
		T = grand_c;
	}
	T->bf = 0;
	unbalanced = false;
}

void right_rotation(tree_ptr T)
{
	tree_ptr grand_c, c;
	c = T->llink;

	if(c->bf == 1)
	{
		T->llink = c->rlink;
		c->rlink = T;
		T->bf = 0;
		T = c;
	}
	else
	{
		grand_c = c->rlink;
		c->rlink = grand_c->llink;
		grand_c->llink = c;
		T->llink = grand_c->rlink;
		grand_c->rlink = T;

		switch(grand_c->bf){
		case 1:
			T->bf = -1;
			c->bf = 0;
			break;
			
		case 0:
			T->bf = c->bf = 0;
			break;
		case -1:
			T->bf = 0;
			c->bf = 1;
		}
		T = grand_c;
	}
	T->bf = 0;
	unbalanced = false;
}

void inorder(tree_ptr node)		// in-order : LVR
{
	if(node) {
		inorder(node->llink);
		if(flag_arrow){
			printf("-> %d ", node->key);
		}else{
			printf("%d ", node->key);
			flag_arrow = true;
		}
		inorder(node->rlink);
	}
}

void preorder(tree_ptr node)	// pre-order : VLR
{
	if(node) {
		if(flag_arrow){
			printf("-> %d ", node->key);
		}else{
			printf("%d ", node->key);
			flag_arrow = true;
		}
		preorder(node->llink);
		preorder(node->rlink);
	}
}

void postorder(tree_ptr node)	// post-order : LRV
{
	if(node) {
		postorder(node->llink);
		postorder(node->rlink);
		if(flag_arrow){
			printf("-> %d ", node->key);
		}else{
			printf("%d ", node->key);
			flag_arrow = true;
		}
	}
}